class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        num_list = [str(i) for i in range(1, n + 1)]
        jiecheng = []
        m = 1
        for i in range(1, n + 1):
            m = m * i
            jiecheng.append(m)
        s = ''
        k = k - 1
        for j in range(n - 1):
            num = k // jiecheng[n - 1 - j - 1]
            s += num_list[num]
            del num_list[num]
            k -= num * jiecheng[n - 1 - j - 1]
        s += num_list[-1]
        return s


data = Solution()
n = 3
k = 1
print(data.getPermutation(n, k))
